Abstract:
The algorithmic challenge of maximizing information diffusion through word-of-mouth processes in social networks has been heavily studied in the past decade. Despite immense progress and an impressive arsenal of techniques, the algorithmic framework makes idealized assumptions regarding access to the network that can often result in poor performance of state-of-the-art techniques.

In this work we introduce a new framework which we call Adaptive Seeding. The framework is a two-stage stochastic optimization model designed to leverage the high potential that typically lies in neighboring nodes of arbitrary samples of social networks. Our main result is an algorithm which is a constant factor approximation of the optimal adaptive policy for any influence function in the Triggering model.